package main.sort;

/**
 * Created by july on 2015/12/24.
 * 冒泡排序：
 *  一种交换排序，基本思想是，两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
 *  设数组长度为N。
 * 1．比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两数据交换。
 * 2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
 * 3．最坏的情况下经过N-1次遍历就可以完成排序。
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] unSorted  = {10,23,32,2,45,6,77,65,27,8};
        bubble(unSorted);
        for(int i:unSorted){
            System.out.print(i + " ");
        }
        System.out.print("\n");


        int[] unSorted1 = {10, 23, 32,2,45,6,77,65,27,8};
        bubble1(unSorted1);
        for(int i:unSorted1){
            System.out.print(i + " ");
        }
        System.out.print("\n");


        int[] unSorted2 = {10,23,32,2,45,6,77,65,27,8};
        bubble2(unSorted2);
        for(int i:unSorted2){
            System.out.print(i + " ");
        }
    }

    /**初始状态：10  23  32  2   45  6  77  65  27  8           循环次数    交换次数
     * 第1趟后： 2   23  32  10  45  6  77  65  27  8           9          1
     * 第2趟后： 2   6   32  23  45  10 77  65  27  8           8          2
     * 第3趟后： 2   6   8   32  45  23 77  65  27  10          7          3
     * 第4趟后： 2   6   8   10  45  32 77  65  27  23          6          2
     * 第5趟后： 2   6   8   10  23  45 77  65  32  27          5          3
     * 第6趟后： 2   6   8   10  23  27 77  65  45  32          4          2
     * 第7趟后： 2   6   8   10  23  27 32  77  65  45          3          3
     * 第8趟后： 2   6   8   10  23  27 32  45  77  65          2          2
     * 第9趟后： 2   6   8   10  23  27 32  45  65  77          1          1
     *                                                   总计： 45次       19次
     * @param unSorted
     */
    private static void bubble(int[] unSorted) {
        int loopCount = 0,swapCount = 0;
        for(int i=0;i<unSorted.length;i++){
            for(int j=i+1;j<unSorted.length;j++){
                if(unSorted[i] > unSorted[j]){
                    int temp = unSorted[i];
                    unSorted[i] = unSorted[j];
                    unSorted[j] = temp;
                    swapCount++;
                }
                loopCount++;
            }
        }
        System.out.println("循环次数：" + loopCount);
        System.out.println("交换次数：" + swapCount);
    }

    /**初始状态：10  23  32  2   45  6  77  65  27  8           循环次数    交换次数
     * 第1趟后： 2   23  32  6   45  8  77  65  27  10          9          3
     * 第2趟后： 2   6   32  8   45  10 77  65  27  23          8          3
     * 第3趟后： 2   6   8   10  45  23 77  65  27  32          7          3
     * 第4趟后： 2   6   8   10  45  23 77  65  27  32          6          0
     * 第5趟后： 2   6   8   10  23  27 77  65  32  45          5          3
     * 第6趟后： 2   6   8   10  23  27 77  65  32  45          4          0
     * 第7趟后： 2   6   8   10  23  27 32  65  45  77          3          2
     * 第8趟后： 2   6   8   10  23  27 32  45  65  77          2          1
     * 第9趟后： 2   6   8   10  23  27 32  45  65  77          1          0
     *                                                   总计： 45次       15次
     * @param unSorted
     */
    private static void bubble1(int[] unSorted){
        int loopCount = 0,swapCount = 0;
        for(int i=0;i<unSorted.length;i++){
            for(int j=unSorted.length-1;j>i;j--){
                if(unSorted[i] > unSorted[j]){
                    int temp = unSorted[i];
                    unSorted[i] = unSorted[j];
                    unSorted[j] = temp;
                    swapCount++;
                }
                loopCount++;
            }
        }
        System.out.println("循环次数：" + loopCount);
        System.out.println("交换次数：" + swapCount);
    }

    /**
     * 观察上面的排序方法，会发现其中有几趟未交换任何数据，所以加入一个条件可以减少循环比较的次数
     * @param unSorted
     */
    private static void bubble2(int[] unSorted){
        int loopCount = 0,swapCount = 0;
        for(int i=0;i<unSorted.length;i++){
            for(int j=unSorted.length-1;j>i;j--){
                if(unSorted[j] > unSorted[j-1]){
                    continue;
                }
                if(unSorted[i] > unSorted[j]){
                    int temp = unSorted[i];
                    unSorted[i] = unSorted[j];
                    unSorted[j] = temp;
                    swapCount++;
                }
                loopCount++;
            }
        }
        System.out.println("循环次数：" + loopCount);
        System.out.println("交换次数：" + swapCount);
    }
}
